import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/14 10:40
 * @description
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    class WordFilter {
        Map<String, List<Integer>> map;
        String[] words;

        public WordFilter(String[] words) {
            this.map = new HashMap<>();
            this.words = words;
            for (int i = 0; i < words.length; i++) {
                String s = words[i];
                StringBuilder sb = new StringBuilder();
                for (char c : s.toCharArray()) {
                    sb.append(c);
                    String curPrefix = sb.toString();
                    if (!map.containsKey(curPrefix)) {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        map.put(curPrefix, list);
                    } else {
                        map.get(curPrefix).add(i);
                    }
                }
            }
        }

        public int f(String prefix, String suffix) {
            if (!map.containsKey(prefix)) {
                return -1;
            }
            List<Integer> list = map.get(prefix);
            return find(list, suffix.toCharArray());
        }

        private int find(List<Integer> list, char[] sstr) {
            for (int i = list.size() - 1; i >= 0; i--) {
                int curIndex = list.get(i);
                char[] curstr = words[curIndex].toCharArray();
                if (curstr.length < sstr.length) {
                    continue;
                }
                int ii = curstr.length - 1, jj = sstr.length - 1;
                boolean choose = true;
                while (jj >= 0) {
                    if (curstr[ii--] != sstr[jj--]) {
                        choose = false;
                        break;
                    }
                }
                if (choose) {
                    return curIndex;
                }
            }
            return -1;
        }
    }
}

